"""
NC13 二叉树的最大深度

https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=117&&tqId=37721&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""
from queue import Queue


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#


class Solution:
    def method1(self, root: TreeNode) -> int:
        """
        自己先想了一个
        不如method2，套路的实现
        """
        if not root:
            return 0

        depth = 1
        nodes = [root]
        while True:
            tmp = []
            for node in nodes:
                if node.left:
                    tmp.append(node.left)

                if node.right:
                    tmp.append(node.right)

            if len(tmp) > 0:
                depth += 1
                nodes = tmp[:]
            else:
                break
        return depth

    def method2(self, root: TreeNode) -> int:
        """
        广度优先算法
        """
        if not root:
            return 0

        depth = 0
        q = Queue()
        q.put(root)
        while not q.empty():
            size = q.qsize()
            for i in range(size):
                node = q.get()
                # 添加下一层的左右节点
                if node.left:
                    q.put(node.left)

                if node.right:
                    q.put(node.right)
            depth += 1

        return depth

    def method3(self, root: TreeNode) -> int:
        """
        递归
        """
        # 空节点没有深度
        if not root:
            return 0
        # 返回子树深度+1
        max_depth = max([self.method3(root.left), self.method3(root.right)])+1
        return max_depth

    def maxDepth(self, root: TreeNode) -> int:
        # write code here
        return self.method1(root)
